<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8" />
  <meta name="referrer" content="never" />
  
  
  <meta name="description" content="用于总结个人学习数据结构的过程。" />
  

  
  
  <meta name="google-site-verification" content="NCXVSqxqB-os803-VFMtIEd1SUNJVOIjctCfNYUwD0w" />
  <meta name="baidu-site-verification" content="Nzwx7HuplM" />
  
  <meta name="msvalidate.01" content="9E9EA92F7E5327E1FE8A5196D5253664" />
  
  
  
  <title>Date Structor ---  数据结构 | masuo777的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="用于总结个人学习数据结构的过程。">
<meta property="og:type" content="article">
<meta property="og:title" content="Date Structor ---  数据结构">
<meta property="og:url" content="https://masuo777.github.io/2021/09/15/DateStructor/index.html">
<meta property="og:site_name" content="masuo777的博客">
<meta property="og:description" content="用于总结个人学习数据结构的过程。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210930172255.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210930172532.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210928112409.jpeg">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210929140711.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210929154112.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210929160310.png">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NDQ1Ny8yMDE3MDIvMTA5NDQ1Ny0yMDE3MDIyNTE4MzYxMDYzMi0xMzg4OTU5NjkxLnBuZw">
<meta property="og:image" content="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NDQ1Ny8yMDE3MDIvMTA5NDQ1Ny0yMDE3MDIyNTE4MzIzNjUzOC05NjE3NTgxNjMucG5n">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220317133208.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211202091743.png">
<meta property="og:image" content="g:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091609815.png">
<meta property="og:image" content="g:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091503800.png">
<meta property="og:image" content="g:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091539517.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211202091743.png">
<meta property="og:image" content="g:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091609815.png">
<meta property="og:image" content="g:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091503800.png">
<meta property="og:image" content="g:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091539517.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215173253.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/image-20211215201354275.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/image-20211215201414293.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215172808.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215174737.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215174753.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121094758.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121102526.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121102541.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121102632.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121103417.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121103528.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121105644.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121105706.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121105733.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211124093637.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331111312.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331114357.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331143949.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402152541.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331144103.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402152958.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153014.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153025.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153037.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153048.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220329171459.png">
<meta property="og:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220330092317.png">
<meta property="article:published_time" content="2021-09-14T16:00:00.000Z">
<meta property="article:modified_time" content="2022-04-02T09:55:46.883Z">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210930172255.png">
  
    <link rel="alternative" href="/atom.xml" title="masuo777的博客" type="application/atom+xml">
  
  
    <link rel="icon" href="http://7u2hdm.com1.z0.glb.clouddn.com/favicon.ico">
  
  
<link rel="stylesheet" href="/css/style.css">

  

  
  <!-- baidu webmaster push -->
  <script src='//push.zhanzhang.baidu.com/push.js'></script>
<meta name="generator" content="Hexo 5.4.0"></head>
<body class="home blog custom-background custom-font-enabled single-author">
  <div id="page" class="hfeed site">
      <header id="masthead" class="site-header" role="banner">
    <hgroup>
      <h1 class="site-title">
        <a href="/" title="masuo777的博客" rel="home">masuo777的博客</a>
      </h1>
      
        <script type="text/javascript" src="http://api.hitokoto.us/rand?encode=js&charset=utf-8"></script>
        <h2 class="site-description"><script>hitokoto();</script></h2>
      
    </hgroup>

    <nav id="site-navigation" class="main-navigation" role="navigation">
            <button class="menu-toggle">菜单</button>
            <a class="assistive-text" href="/#content" title="跳至内容">跳至内容</a><!--TODO-->
            <div class="menu-main-container">
                <ul id="menu-main" class="nav-menu">
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/">MDS</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/todo">ToDo</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/images">images</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/about">ME</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/works">作品集</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a href="/tools">工具集</a></li>
                
                    <li class="menu-item menu-item-type-post_type menu-item-object-page"><a target="_blank" rel="noopener" href="https://github.com/Masuo777">my github</a></li>
                
                </ul>
            </div>
    </nav>
</header>
      <div id="main" class="wrapper">
        <div id="primary" class="site-content"><div id="content" role="main"><article id="post-DateStructor" class="post-DateStructor post type-post status-publish format-standard hentry">
    <!---->

      <header class="entry-header">
        
        
  
    <h1 class="entry-title article-title">
      Date Structor ---  数据结构
    </h1>
  

        
        <div class="comments-link">
            
            <a href="/2021/09/15/DateStructor/#comments" class="leave-reply">评论</a>
            
            <a href="javascript:void(0);" data-url="https://masuo777.github.io/2021/09/15/DateStructor/" data-id="cl3jit8n500032ojb4s7j6s9c" class="leave-reply bdsharebuttonbox" data-cmd="more">分享</a>
        </div><!-- .comments-link -->
      </header><!-- .entry-header -->

    <div class="entry-content">
      
        <h1 id="Date-Structor"><a href="#Date-Structor" class="headerlink" title="Date Structor"></a>Date Structor</h1><blockquote>
<h5 id="数据结构就是一系列有一定关联的数据集合在计算机中的一种特殊的存储形式。"><a href="#数据结构就是一系列有一定关联的数据集合在计算机中的一种特殊的存储形式。" class="headerlink" title="数据结构就是一系列有一定关联的数据集合在计算机中的一种特殊的存储形式。"></a>数据结构就是一系列有一定关联的数据集合在计算机中的一种特殊的存储形式。</h5><p>最经典的数据结构包括<strong>数组</strong>（array list）、<strong>链表</strong>（linked list）、<strong>队列</strong>（queue）、<strong>栈</strong>（stack）、<strong>堆</strong>（heap）、<strong>树</strong>（tree）、<strong>图</strong>（map）、<strong>散列表</strong>（hash）。</p>
</blockquote>
<p>接下来的一到两个月里，我们来一一实现这些数据结构吧。</p>
<blockquote>
<h4 id="数组和链表是最基础的两大数据结构，下面的数据结构大多都是依靠这两种数据结构完成的，可以说是他们的深层扩展。"><a href="#数组和链表是最基础的两大数据结构，下面的数据结构大多都是依靠这两种数据结构完成的，可以说是他们的深层扩展。" class="headerlink" title="数组和链表是最基础的两大数据结构，下面的数据结构大多都是依靠这两种数据结构完成的，可以说是他们的深层扩展。"></a>数组和链表是最基础的两大数据结构，下面的数据结构大多都是依靠这两种数据结构完成的，可以说是他们的深层扩展。</h4></blockquote>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210930172255.png" alt="image-20210930172254001"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210930172532.png" alt="image-20210930172530254"></p>
<p>图片来源：<a target="_blank" rel="noopener" href="https://www.bigocheatsheet.com/">https://www.bigocheatsheet.com/</a></p>
<span id="more"></span>

<h2 id="数组（array-list）"><a href="#数组（array-list）" class="headerlink" title="数组（array list）"></a><strong>数组</strong>（array list）</h2><h2 id="链表（linked-list）"><a href="#链表（linked-list）" class="headerlink" title="链表（linked list）"></a><strong>链表</strong>（linked list）</h2><h2 id="队列（queue）"><a href="#队列（queue）" class="headerlink" title="队列（queue）"></a><strong>队列</strong>（queue）</h2><h2 id="栈（stack）"><a href="#栈（stack）" class="headerlink" title="栈（stack）"></a><strong>栈</strong>（stack）</h2><h2 id="堆（heap）"><a href="#堆（heap）" class="headerlink" title="堆（heap）"></a><strong>堆</strong>（heap）</h2><h2 id="树（tree）"><a href="#树（tree）" class="headerlink" title="树（tree）"></a><strong>树</strong>（tree）</h2><blockquote>
<p>先不说树得定义是什么，那些术语让人头疼，极易劝退我们这些脑子转的慢的。</p>
</blockquote>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210928112409.jpeg" alt="img"></p>
<blockquote>
<p>我们先在脑海中或向窗外看去（看上图也可），树的形象就那样（暂时不考虑树根的形状），由有限的的树枝和树叶组成，连接树枝和树叶的我们且称为线吧，树干虽然跟树枝有点区别，但是他也算大个儿的树枝，所以一个树就是由<strong>根，树枝，树叶，边</strong>组成的。在计算机中的一棵树，其实就是将抽象出来的树以数据结构的形式体现在计算机中，他存储的话还是以<strong>链表</strong>为底层的存储结构。</p>
</blockquote>
<blockquote>
<h5 id="树是由节点或顶点和边组成的且不存在环的一种数据结构。"><a href="#树是由节点或顶点和边组成的且不存在环的一种数据结构。" class="headerlink" title="树是由节点或顶点和边组成的且不存在环的一种数据结构。"></a>树是由节点或顶点和边组成的且不存在环的一种数据结构。</h5></blockquote>
<h3 id="树的术语"><a href="#树的术语" class="headerlink" title="树的术语"></a>树的术语</h3><ul>
<li>节点深度：对任意节点X，X节点的深度表示<strong>根节点</strong>到<strong>X节点</strong>的<strong>路径长度</strong>。</li>
<li>节点高度：对任意节点X，X节点的高度表示<strong>叶子节点</strong>到<strong>X节点</strong>的<strong>路径长度</strong>。</li>
<li>树的深度(高度)：一棵树中 ”max(节点深度)” 就是树的深度。</li>
<li>父节点：若一个节点有子节点，则此节点为其子节点的父节点</li>
<li>子节点：小树枝</li>
<li>节点的层次：根为第一层，其子节点为第二层，即 层次=节点深度+1</li>
<li>兄弟节点，父节点的子节点们互为兄弟节点。</li>
<li>度：子节点的数目为度，如二叉树的度为2.</li>
<li>叶子节点：无子节点的节点为叶子节点</li>
<li>祖先：从子节点到父节点的重复操作可以到达的节点</li>
<li>后代：从父结点到子节点的重复操作可以到达的节点</li>
<li>森林：互不相交的树形成森林</li>
</ul>
<h3 id="树的种类"><a href="#树的种类" class="headerlink" title="树的种类"></a><strong>树的种类</strong></h3><h4 id="无序树"><a href="#无序树" class="headerlink" title="无序树"></a>无序树</h4><blockquote>
<p>树的任意节点的字节点没有顺序关系</p>
</blockquote>
<h4 id="有序树"><a href="#有序树" class="headerlink" title="有序树"></a>有序树</h4><blockquote>
<p>树的任意节点的子节点有顺序关系</p>
</blockquote>
<h4 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h4><blockquote>
<p>树的任意节点至多有两个子节点</p>
</blockquote>
<h5 id="实现"><a href="#实现" class="headerlink" title="实现"></a>实现</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> dataStructure.tree;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> masuo</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@data</span> 2021/9/28 10:03</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 树型数据结构应用非常广泛，尤其是在大数据查询方面，其次文件结构大多也是树形结构</span></span><br><span class="line"><span class="comment"> *	应用最多的就是二叉树，</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">SimpleBinaryTree</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//简单二叉树结构---静态二叉树，提供构建二叉树的结构，但是需要自己构建二叉树，</span></span><br><span class="line">    <span class="comment">//二叉树通用结构有两个子节点，一个父节点，值</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; root;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//高度</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> height;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">SimpleBinaryTree</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.root = <span class="keyword">new</span> Node&lt;&gt;();</span><br><span class="line">        <span class="keyword">this</span>.height = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//&#123; 2 , 5 , 9 , 7 , 3&#125;,</span></span><br><span class="line">        Node&lt;Integer&gt; n1 = <span class="keyword">new</span> Node&lt;&gt;(<span class="number">2</span>);</span><br><span class="line">        Node&lt;Integer&gt; n2 = <span class="keyword">new</span> Node&lt;&gt;(<span class="number">5</span>);</span><br><span class="line">        Node&lt;Integer&gt; n3 = <span class="keyword">new</span> Node&lt;&gt;(<span class="number">9</span>);</span><br><span class="line">        Node&lt;Integer&gt; n4 = <span class="keyword">new</span> Node&lt;&gt;(<span class="number">7</span>);</span><br><span class="line">        Node&lt;Integer&gt; n5 = <span class="keyword">new</span> Node&lt;&gt;(<span class="number">3</span>);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//树结构，构建树</span></span><br><span class="line">        <span class="comment">//      2</span></span><br><span class="line">        <span class="comment">//  5       9</span></span><br><span class="line">        <span class="comment">//       7      3</span></span><br><span class="line">        n1.leftSon = n2;</span><br><span class="line">        n1.rightSon = n3;</span><br><span class="line">        n3.leftSon = n4;</span><br><span class="line">        n3.rightSon = n5;</span><br><span class="line"></span><br><span class="line">        SimpleBinaryTree&lt;Integer&gt; sbt = <span class="keyword">new</span> SimpleBinaryTree&lt;&gt;();</span><br><span class="line">        sbt.root = n1;</span><br><span class="line">        sbt.test();</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">test</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="comment">//先序</span></span><br><span class="line">        firstOrder(root);</span><br><span class="line">        System.out.println(<span class="string">&quot;先序结束&quot;</span>);</span><br><span class="line">        <span class="comment">//中序</span></span><br><span class="line">        midOrder(root);</span><br><span class="line">        System.out.println(<span class="string">&quot;中序结束&quot;</span>);</span><br><span class="line">        <span class="comment">//后序</span></span><br><span class="line">        lastOrder(root);</span><br><span class="line">        System.out.println(<span class="string">&quot;后序结束&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//这些遍历输出的思想其实很简单，就是高中的整体思想，将左儿子与右儿子当成一个整体去代入</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">firstOrder</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (<span class="keyword">null</span> != node)&#123;</span><br><span class="line">            System.out.println(node.item);</span><br><span class="line">            Node&lt;E&gt; left = node.leftSon;</span><br><span class="line">            Node&lt;E&gt; right = node.rightSon;</span><br><span class="line">            <span class="keyword">if</span>(left != <span class="keyword">null</span>)&#123;</span><br><span class="line">                firstOrder(left);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(right != <span class="keyword">null</span>)&#123;</span><br><span class="line">                firstOrder(right);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">midOrder</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">            Node&lt;E&gt; left = node.leftSon;</span><br><span class="line">            Node&lt;E&gt; right = node.rightSon;</span><br><span class="line">            <span class="keyword">if</span>(left != <span class="keyword">null</span>)&#123;</span><br><span class="line">                midOrder(left);</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(node.item);</span><br><span class="line">            <span class="keyword">if</span>(right != <span class="keyword">null</span>)&#123;</span><br><span class="line">                midOrder(right);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">lastOrder</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">            Node&lt;E&gt; left = node.leftSon;</span><br><span class="line">            Node&lt;E&gt; right = node.rightSon;</span><br><span class="line">            <span class="keyword">if</span>(left != <span class="keyword">null</span>)&#123;</span><br><span class="line">                lastOrder(left);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(right != <span class="keyword">null</span>)&#123;</span><br><span class="line">                lastOrder(right);</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.println(node.item);</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//树是由 节点 和 边 构成</span></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">E</span>&gt;</span>&#123;</span><br><span class="line">        <span class="comment">//值</span></span><br><span class="line">        E item;</span><br><span class="line">        <span class="comment">//父节点，可有可无</span></span><br><span class="line">        <span class="comment">//Node&lt;E&gt; father;</span></span><br><span class="line">        <span class="comment">//左儿子</span></span><br><span class="line">        Node&lt;E&gt; leftSon;</span><br><span class="line">        <span class="comment">//右儿子</span></span><br><span class="line">        Node&lt;E&gt; rightSon;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.item = item;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="缺点"><a href="#缺点" class="headerlink" title="缺点"></a>缺点</h5><ul>
<li>无序，需手动构建</li>
</ul>
<h4 id="二叉查找树"><a href="#二叉查找树" class="headerlink" title="二叉查找树"></a>二叉查找树</h4><blockquote>
<p>二叉查找树又叫二叉搜索树，是指一棵空树或者具有下列性质的二叉树：</p>
<ol>
<li>若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；</li>
</ol>
<p>　2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；</p>
<p>　3. 任意节点的左、右子树也分别为二叉查找树。</p>
<p>　4. 没有键值相等的节点（no duplicate nodes）。</p>
</blockquote>
<h5 id="实现-1"><a href="#实现-1" class="headerlink" title="实现"></a>实现</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> dataStructure.tree;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.NoSuchElementException;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> masuo</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@data</span> 2021/9/29 10:07</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 动态二叉树--提供构建二叉树的结构，再增加数据时自动构建二叉树</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DynamicBinaryTree</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//树根</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; root;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//树高</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> height;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//修改次数</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> modCount;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//是否被修改</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">boolean</span> modCountFlag;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">DynamicBinaryTree</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.modCountFlag = <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//增加节点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">add</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) &#123;</span><br><span class="line">            root = <span class="keyword">new</span> Node&lt;&gt;(item);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            Node&lt;E&gt; newNode = <span class="keyword">new</span> Node&lt;&gt;(item);</span><br><span class="line">            Node&lt;E&gt; temp = root;</span><br><span class="line">            <span class="keyword">while</span> (<span class="keyword">true</span>) &#123;</span><br><span class="line">                <span class="keyword">if</span> (item.hashCode() &lt; temp.item.hashCode()) &#123;</span><br><span class="line">                    <span class="comment">//插入左</span></span><br><span class="line">                    <span class="keyword">if</span> (temp.leftSon == <span class="keyword">null</span>) &#123;</span><br><span class="line">                        temp.leftSon = newNode;</span><br><span class="line">                        newNode.parent = temp;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    temp = temp.leftSon;</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    <span class="comment">//插入右</span></span><br><span class="line">                    <span class="keyword">if</span> (temp.rightSon == <span class="keyword">null</span>) &#123;</span><br><span class="line">                        temp.rightSon = newNode;</span><br><span class="line">                        newNode.parent = temp;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    temp = temp.rightSon;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//修改次数+1</span></span><br><span class="line">        ++modCount;</span><br><span class="line">        <span class="comment">//修改增加标识为true</span></span><br><span class="line">        modCountFlag = <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查找节点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Node&lt;E&gt; <span class="title">get</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">        Node&lt;E&gt; temp = root;</span><br><span class="line">        <span class="keyword">while</span> (temp != <span class="keyword">null</span> &amp;&amp; temp.item != item) &#123;</span><br><span class="line">            <span class="keyword">if</span> (item.hashCode() &lt; temp.item.hashCode()) &#123;</span><br><span class="line">                <span class="comment">//在左侧找</span></span><br><span class="line">                temp = temp.leftSon;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//在右侧找</span></span><br><span class="line">                temp = temp.rightSon;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> temp;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">del</span><span class="params">(E value)</span> </span>&#123;</span><br><span class="line">        Node&lt;E&gt; delNode = get(value);</span><br><span class="line">        checkNode(delNode);</span><br><span class="line">        ++modCount;</span><br><span class="line">        modCountFlag = <span class="keyword">true</span>;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//判断是否有左子树</span></span><br><span class="line">        <span class="keyword">if</span> (delNode.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="comment">//有左子树则有两种情况。一种是左子树有</span></span><br><span class="line">            Node&lt;E&gt; maxNode = getMaxLeaf(delNode.leftSon);</span><br><span class="line">            delNode.item = maxNode.item;</span><br><span class="line">            <span class="keyword">if</span>(delNode.leftSon.rightSon != <span class="keyword">null</span>)&#123;</span><br><span class="line">                <span class="comment">//说明左子树的右子树不为空，最大值取值为右子树的叶子节点</span></span><br><span class="line">                maxNode.parent.rightSon = <span class="keyword">null</span>;</span><br><span class="line">            &#125;<span class="keyword">else</span> &#123;</span><br><span class="line">                delNode.leftSon = maxNode.leftSon;</span><br><span class="line">                maxNode.parent = delNode.parent;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//没有左子树且右子树不为空则直接将右子树连接到父节点</span></span><br><span class="line">            <span class="keyword">if</span> (delNode.parent.leftSon == delNode) &#123;</span><br><span class="line">                delNode.parent.leftSon = delNode.rightSon;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                delNode.parent.rightSon = delNode.rightSon;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 获取自 node 结点开始的最大的节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 开始节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 最大节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Node&lt;E&gt; <span class="title">getMaxLeaf</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//根据二叉查找树的特点，大的都在节点右侧</span></span><br><span class="line">        <span class="comment">//首先判断右子树是否为空</span></span><br><span class="line">        <span class="keyword">while</span> (node.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            node = node.rightSon;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//右子树为空则返回node本身</span></span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">checkNode</span><span class="params">(Node&lt;E&gt; temp)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (temp == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException();</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getHeight</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (!modCountFlag) &#123;</span><br><span class="line">            <span class="keyword">return</span> height;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            height = calHeight(root);</span><br><span class="line">            modCountFlag = <span class="keyword">false</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> height;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">calHeight</span><span class="params">(Node&lt;E&gt; n)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (n.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            left = calHeight(n.leftSon);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (n.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            right = calHeight(n.rightSon);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> Math.max(left, right) + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//二叉树节点</span></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line">        <span class="keyword">transient</span> E item;</span><br><span class="line">        Node&lt;E&gt; parent;</span><br><span class="line">        Node&lt;E&gt; leftSon;</span><br><span class="line">        Node&lt;E&gt; rightSon;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.item = item;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(E item, Node&lt;E&gt; leftSon, Node&lt;E&gt; rightSon, Node&lt;E&gt; parent)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.item = item;</span><br><span class="line">            <span class="keyword">this</span>.leftSon = leftSon;</span><br><span class="line">            <span class="keyword">this</span>.rightSon = rightSon;</span><br><span class="line">            <span class="keyword">this</span>.parent = parent;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="测试"><a href="#测试" class="headerlink" title="测试"></a>测试</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">@Test</span></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">test1</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="comment">//&#123; 2 , 5 , 9 , 7 , 3&#125;</span></span><br><span class="line">    DynamicBinaryTree&lt;Integer&gt; dbt = <span class="keyword">new</span> DynamicBinaryTree&lt;&gt;();</span><br><span class="line">    dbt.add(<span class="number">10</span>);</span><br><span class="line">    dbt.add(<span class="number">5</span>);</span><br><span class="line">    dbt.add(<span class="number">15</span>);</span><br><span class="line">    dbt.add(<span class="number">12</span>);</span><br><span class="line">    dbt.add(<span class="number">17</span>);</span><br><span class="line">    dbt.add(<span class="number">11</span>);</span><br><span class="line">    dbt.add(<span class="number">13</span>);</span><br><span class="line">    dbt.add(<span class="number">16</span>);</span><br><span class="line">    dbt.add(<span class="number">18</span>);</span><br><span class="line">    System.out.println(dbt.get(<span class="number">5</span>).item);</span><br><span class="line">    dbt.del(<span class="number">5</span>);</span><br><span class="line">    dbt.del(<span class="number">15</span>);</span><br><span class="line">    dbt.del(<span class="number">12</span>);</span><br><span class="line">    dbt.del(<span class="number">13</span>);</span><br><span class="line">    System.out.println(dbt.getHeight());</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="缺点-1"><a href="#缺点-1" class="headerlink" title="缺点"></a>缺点</h5><ul>
<li><p>查找</p>
<ul>
<li>查找任何一个数据都要从根节点开始，沿着一个路径往下找，因此查找时的比较次数与树得形态密切相关。</li>
<li>当树根的左右树高度相近时，此时树高为<strong>LogN</strong>,查询效率较高，时间复杂度为O（logN）。</li>
<li>当插入数据为有序数组时，树结构变成线性链表，查询效率最低，如下图，此时树高为：N，平均查找长度为：（N+1）/2，时间复杂度为O（logN）</li>
</ul>
<p>  <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210929140711.png" alt="image-20210929140707280"></p>
</li>
<li><p>插入</p>
<ul>
<li>插入的前提是找到插入位置，等同于查询，只是多了一个插入操作。</li>
</ul>
</li>
<li><p>删除</p>
<ul>
<li><p>删除设计到了数据的移动，由于树有两个子节点，当删除的节点没有两个子节点的时候，删除的时间复杂度为O（1），当删除的节点涉及到两个子节点的时候，就需要移动数据。</p>
<p>  以下图为例：删除节点15，找左子树的右子树直到叶子，因为二叉搜索树的规则是左子树都小于根节点，右子树都大于根节点，详细步骤为：</p>
<p>  ① 首先找到节点15</p>
<p>  ② 找他是否有左子树，有则③，没有则④</p>
<p>  ③ 判断其左子树是否有右子树，有则⑤，</p>
<p>  ④ 判断其是否有右子树，有则连接其右子树，没有则直接删除。</p>
<p>  ⑤ 判断其右子树是否有右子树，然后重复⑤，直到找到叶子节点。</p>
<p>  使用工具为：<a target="_blank" rel="noopener" href="https://www.cs.usfca.edu/~galles/visualization/BST.html">https://www.cs.usfca.edu/~galles/visualization/BST.html</a></p>
<p>  <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210929154112.png" alt="image-20210929154110814"></p>
<p>  删除完成之后：<img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210929160310.png" alt="image-20210929160308427"></p>
</li>
</ul>
</li>
</ul>
<h4 id="满二叉树"><a href="#满二叉树" class="headerlink" title="满二叉树"></a>满二叉树</h4><blockquote>
<p>A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.</p>
</blockquote>
<blockquote>
<p>深度为k且有2^k-1个结点的二叉树称为满二叉树（Full Binary Tree）</p>
</blockquote>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NDQ1Ny8yMDE3MDIvMTA5NDQ1Ny0yMDE3MDIyNTE4MzYxMDYzMi0xMzg4OTU5NjkxLnBuZw" alt="img"></p>
<p>$$<br>满二叉树中节点数=2^k-1,k是树的深度<br>$$</p>
<h4 id="完全二叉树"><a href="#完全二叉树" class="headerlink" title="完全二叉树"></a>完全二叉树</h4><blockquote>
<p>设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。</p>
<p>即树是从上到下从左到右依次排列的二叉树。</p>
</blockquote>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTA5NDQ1Ny8yMDE3MDIvMTA5NDQ1Ny0yMDE3MDIyNTE4MzIzNjUzOC05NjE3NTgxNjMucG5n" alt="img"></p>
<p>非完全二叉树（❌代表没有节点，此时由于从左到右节点没有依次排列，不构成完全二叉树）</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220317133208.png" alt="image-20220317133208544"></p>
<h4 id="平衡二叉树"><a href="#平衡二叉树" class="headerlink" title="平衡二叉树"></a>平衡二叉树</h4><blockquote>
<p>平衡二叉树也叫AVL树，它是二叉查找树的进阶版，由于二叉查找树存在一定的局限性，所以衍生出了平衡二叉树。</p>
<p>它是一棵空树或左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。<strong>AVL树</strong>是最早被发明的<a href="https://link.zhihu.com/?target=https://zh.wikipedia.org/wiki/%E8%87%AA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%9F%A5%E6%89%BE%E6%A0%91">自平衡二叉查找树</a>。</p>
</blockquote>
<blockquote>
<p>这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。</p>
<p>增加和删除元素的操作则可能需要借由一次或多次<a href="https://link.zhihu.com/?target=https://zh.wikipedia.org/wiki/%E6%A0%91%E6%97%8B%E8%BD%AC">树旋转</a>，以实现树的重新平衡。AVL 树得名于它的发明者 <a href="https://link.zhihu.com/?target=https://zh.wikipedia.org/wiki/%E6%A0%BC%E5%A5%A5%E5%B0%94%E5%90%89%C2%B7%E9%98%BF%E6%9D%B0%E5%B0%94%E6%9D%BE-%E9%9F%A6%E5%88%A9%E6%96%AF%E5%9F%BA">G. M. Adelson-Velsky</a> 和 <a href="https://link.zhihu.com/?target=https://zh.wikipedia.org/w/index.php?title=Evgenii_Landis&action=edit&redlink=1">Evgenii Landis</a>，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。</p>
</blockquote>
<blockquote>
<p>但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。</p>
</blockquote>
<h5 id="二叉查找树的问题及解决"><a href="#二叉查找树的问题及解决" class="headerlink" title="二叉查找树的问题及解决"></a>二叉查找树的问题及解决</h5><p>不平衡的产生条件就是违背了平衡二叉树的定义—左右两子树的高度差，即节点的平衡因子绝对值小于等于1，那不平衡的情况无非以下两种：    </p>
<p>① 左高右低，左子树的高度大于右子树的高度，且高度差大于1（这里一般就是2，不会再高了基本上）</p>
<p>② 右高左低，右子树的高度大于左子树的高度，且高度差大于1</p>
<p>由于树的形状不确定性，以上两种情况的每种情况又可以细分为下面两种情况：</p>
<blockquote>
<p><strong>注意</strong>：以下的‘L’或‘R’,代表的是树的倾斜方向，并不代表旋转方向，旋转方向为倾斜方向的反方向，请勿混淆。</p>
</blockquote>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211202091743.png" alt="image-20211202091412412"><img src="G:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091609815.png" alt="image-20211202091609815"></p>
<p><img src="G:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091503800.png" alt="image-20211202091503800"><img src="G:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091539517.png" alt="image-20211202091539517"></p>
<p>Ⅰ、插入节点位于<strong>最小失衡子树</strong>（节点5）的左子树的左子树</p>
<p>​        <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211202091743.png" alt="image-20211202091412412"></p>
<p>​        这种情况需要<strong>LL平衡旋转</strong>。</p>
<p>Ⅱ、插入节点位于<strong>最低不平衡节点</strong>的左子树的右子树的</p>
<p>​        <img src="G:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091609815.png" alt="image-20211202091609815"></p>
<p>​        这种情况需要<strong>LR平衡旋转</strong>。</p>
<p>Ⅲ、插入节点位于<strong>最小失衡子树</strong>（节点5）的右子树的右子树</p>
<p>​        <img src="G:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091503800.png" alt="image-20211202091503800"></p>
<p>​        这种情况需要<strong>RR平衡旋转</strong>。</p>
<p>Ⅳ、插入节点位于<strong>最小失衡子树</strong>（节点5）的右子树的左子树</p>
<p>​        <img src="G:/%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/image/image-20211202091539517.png" alt="image-20211202091539517"></p>
<p>​        这种情况需要<strong>RL平衡旋转</strong>。</p>
<p>参考：<a target="_blank" rel="noopener" href="https://www.cnblogs.com/skywang12345/p/3576969.html">https://www.cnblogs.com/skywang12345/p/3576969.html</a></p>
<p><strong>最小失衡子树</strong>：从插入节点向上查找，查到的第一个以<strong>平衡因子</strong>绝对值大于1的节点为跟的子树就是最小失衡子树。</p>
<p><strong>平衡因子</strong>：左子树高度 - 右子树高度。</p>
<ul>
<li><p>RR平衡旋转</p>
<ul>
<li><p><strong>条件</strong>：右子树高度 – 左子树高度 &gt;= 2</p>
</li>
<li><p><strong>解决</strong>：左单旋</p>
</li>
<li><p><strong>步骤</strong>：</p>
<p>  <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215173253.png" alt="image-20211215173251031"></p>
</li>
</ul>
</li>
<li><p>RL平衡旋转</p>
<ul>
<li><p><strong>条件</strong>：失衡节点向右倾斜，失衡节点的右子树向左倾斜。</p>
</li>
<li><p><strong>解决</strong>：分别对失衡节点的右子树进行左旋，对失衡节点进行右旋。</p>
</li>
<li><p><strong>步骤</strong>：</p>
<p>  <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/image-20211215201354275.png" alt="image-20211215201354275"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/image-20211215201414293.png" alt="image-20211215201414293"></p>
</li>
</ul>
</li>
<li><p>LL平衡旋转</p>
<ul>
<li><p><strong>条件</strong>：左子树高度 – 右子树高度 &gt;= 2</p>
</li>
<li><p><strong>解决</strong>：右单旋</p>
</li>
<li><p><strong>步骤</strong>：</p>
<p>  <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215172808.png" alt="image-20211215172806314"></p>
</li>
</ul>
</li>
<li><p>LR平衡旋转</p>
<ul>
<li><strong>条件</strong>：失衡节点向左倾斜，失衡节点的左子树向右倾斜。</li>
<li><strong>解决</strong>：</li>
<li><strong>步骤</strong>：</li>
</ul>
<p>  <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215174737.png" alt="image-20211215174735880"><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211215174753.png" alt="image-20211215174751899"></p>
</li>
</ul>
<blockquote>
<p><strong>注意</strong>：以上所有情况均未考虑失衡节点的父节点的情况，因为父节点相对左右旋转比较简单，但是不可不考虑。</p>
</blockquote>
<h5 id="实现-2"><a href="#实现-2" class="headerlink" title="实现"></a>实现</h5><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br><span class="line">178</span><br><span class="line">179</span><br><span class="line">180</span><br><span class="line">181</span><br><span class="line">182</span><br><span class="line">183</span><br><span class="line">184</span><br><span class="line">185</span><br><span class="line">186</span><br><span class="line">187</span><br><span class="line">188</span><br><span class="line">189</span><br><span class="line">190</span><br><span class="line">191</span><br><span class="line">192</span><br><span class="line">193</span><br><span class="line">194</span><br><span class="line">195</span><br><span class="line">196</span><br><span class="line">197</span><br><span class="line">198</span><br><span class="line">199</span><br><span class="line">200</span><br><span class="line">201</span><br><span class="line">202</span><br><span class="line">203</span><br><span class="line">204</span><br><span class="line">205</span><br><span class="line">206</span><br><span class="line">207</span><br><span class="line">208</span><br><span class="line">209</span><br><span class="line">210</span><br><span class="line">211</span><br><span class="line">212</span><br><span class="line">213</span><br><span class="line">214</span><br><span class="line">215</span><br><span class="line">216</span><br><span class="line">217</span><br><span class="line">218</span><br><span class="line">219</span><br><span class="line">220</span><br><span class="line">221</span><br><span class="line">222</span><br><span class="line">223</span><br><span class="line">224</span><br><span class="line">225</span><br><span class="line">226</span><br><span class="line">227</span><br><span class="line">228</span><br><span class="line">229</span><br><span class="line">230</span><br><span class="line">231</span><br><span class="line">232</span><br><span class="line">233</span><br><span class="line">234</span><br><span class="line">235</span><br><span class="line">236</span><br><span class="line">237</span><br><span class="line">238</span><br><span class="line">239</span><br><span class="line">240</span><br><span class="line">241</span><br><span class="line">242</span><br><span class="line">243</span><br><span class="line">244</span><br><span class="line">245</span><br><span class="line">246</span><br><span class="line">247</span><br><span class="line">248</span><br><span class="line">249</span><br><span class="line">250</span><br><span class="line">251</span><br><span class="line">252</span><br><span class="line">253</span><br><span class="line">254</span><br><span class="line">255</span><br><span class="line">256</span><br><span class="line">257</span><br><span class="line">258</span><br><span class="line">259</span><br><span class="line">260</span><br><span class="line">261</span><br><span class="line">262</span><br><span class="line">263</span><br><span class="line">264</span><br><span class="line">265</span><br><span class="line">266</span><br><span class="line">267</span><br><span class="line">268</span><br><span class="line">269</span><br><span class="line">270</span><br><span class="line">271</span><br><span class="line">272</span><br><span class="line">273</span><br><span class="line">274</span><br><span class="line">275</span><br><span class="line">276</span><br><span class="line">277</span><br><span class="line">278</span><br><span class="line">279</span><br><span class="line">280</span><br><span class="line">281</span><br><span class="line">282</span><br><span class="line">283</span><br><span class="line">284</span><br><span class="line">285</span><br><span class="line">286</span><br><span class="line">287</span><br><span class="line">288</span><br><span class="line">289</span><br><span class="line">290</span><br><span class="line">291</span><br><span class="line">292</span><br><span class="line">293</span><br><span class="line">294</span><br><span class="line">295</span><br><span class="line">296</span><br><span class="line">297</span><br><span class="line">298</span><br><span class="line">299</span><br><span class="line">300</span><br><span class="line">301</span><br><span class="line">302</span><br><span class="line">303</span><br><span class="line">304</span><br><span class="line">305</span><br><span class="line">306</span><br><span class="line">307</span><br><span class="line">308</span><br><span class="line">309</span><br><span class="line">310</span><br><span class="line">311</span><br><span class="line">312</span><br><span class="line">313</span><br><span class="line">314</span><br><span class="line">315</span><br><span class="line">316</span><br><span class="line">317</span><br><span class="line">318</span><br><span class="line">319</span><br><span class="line">320</span><br><span class="line">321</span><br><span class="line">322</span><br><span class="line">323</span><br><span class="line">324</span><br><span class="line">325</span><br><span class="line">326</span><br><span class="line">327</span><br><span class="line">328</span><br><span class="line">329</span><br><span class="line">330</span><br><span class="line">331</span><br><span class="line">332</span><br><span class="line">333</span><br><span class="line">334</span><br><span class="line">335</span><br><span class="line">336</span><br><span class="line">337</span><br><span class="line">338</span><br><span class="line">339</span><br><span class="line">340</span><br><span class="line">341</span><br><span class="line">342</span><br><span class="line">343</span><br><span class="line">344</span><br><span class="line">345</span><br><span class="line">346</span><br><span class="line">347</span><br><span class="line">348</span><br><span class="line">349</span><br><span class="line">350</span><br><span class="line">351</span><br><span class="line">352</span><br><span class="line">353</span><br><span class="line">354</span><br><span class="line">355</span><br><span class="line">356</span><br><span class="line">357</span><br><span class="line">358</span><br><span class="line">359</span><br><span class="line">360</span><br><span class="line">361</span><br><span class="line">362</span><br><span class="line">363</span><br><span class="line">364</span><br><span class="line">365</span><br><span class="line">366</span><br><span class="line">367</span><br><span class="line">368</span><br><span class="line">369</span><br><span class="line">370</span><br><span class="line">371</span><br><span class="line">372</span><br><span class="line">373</span><br><span class="line">374</span><br><span class="line">375</span><br><span class="line">376</span><br><span class="line">377</span><br><span class="line">378</span><br><span class="line">379</span><br><span class="line">380</span><br><span class="line">381</span><br><span class="line">382</span><br><span class="line">383</span><br><span class="line">384</span><br><span class="line">385</span><br><span class="line">386</span><br><span class="line">387</span><br><span class="line">388</span><br><span class="line">389</span><br><span class="line">390</span><br><span class="line">391</span><br><span class="line">392</span><br><span class="line">393</span><br><span class="line">394</span><br><span class="line">395</span><br><span class="line">396</span><br><span class="line">397</span><br><span class="line">398</span><br><span class="line">399</span><br><span class="line">400</span><br><span class="line">401</span><br><span class="line">402</span><br><span class="line">403</span><br><span class="line">404</span><br><span class="line">405</span><br><span class="line">406</span><br><span class="line">407</span><br><span class="line">408</span><br><span class="line">409</span><br><span class="line">410</span><br><span class="line">411</span><br><span class="line">412</span><br><span class="line">413</span><br><span class="line">414</span><br><span class="line">415</span><br><span class="line">416</span><br><span class="line">417</span><br><span class="line">418</span><br><span class="line">419</span><br><span class="line">420</span><br><span class="line">421</span><br><span class="line">422</span><br><span class="line">423</span><br><span class="line">424</span><br><span class="line">425</span><br><span class="line">426</span><br><span class="line">427</span><br><span class="line">428</span><br><span class="line">429</span><br><span class="line">430</span><br><span class="line">431</span><br><span class="line">432</span><br><span class="line">433</span><br><span class="line">434</span><br><span class="line">435</span><br><span class="line">436</span><br><span class="line">437</span><br><span class="line">438</span><br><span class="line">439</span><br><span class="line">440</span><br><span class="line">441</span><br><span class="line">442</span><br><span class="line">443</span><br><span class="line">444</span><br><span class="line">445</span><br><span class="line">446</span><br><span class="line">447</span><br><span class="line">448</span><br><span class="line">449</span><br><span class="line">450</span><br><span class="line">451</span><br><span class="line">452</span><br><span class="line">453</span><br><span class="line">454</span><br><span class="line">455</span><br><span class="line">456</span><br><span class="line">457</span><br><span class="line">458</span><br><span class="line">459</span><br><span class="line">460</span><br><span class="line">461</span><br><span class="line">462</span><br><span class="line">463</span><br><span class="line">464</span><br><span class="line">465</span><br><span class="line">466</span><br><span class="line">467</span><br><span class="line">468</span><br><span class="line">469</span><br><span class="line">470</span><br><span class="line">471</span><br><span class="line">472</span><br><span class="line">473</span><br><span class="line">474</span><br><span class="line">475</span><br><span class="line">476</span><br><span class="line">477</span><br><span class="line">478</span><br><span class="line">479</span><br><span class="line">480</span><br><span class="line">481</span><br><span class="line">482</span><br><span class="line">483</span><br><span class="line">484</span><br><span class="line">485</span><br><span class="line">486</span><br><span class="line">487</span><br><span class="line">488</span><br><span class="line">489</span><br><span class="line">490</span><br><span class="line">491</span><br><span class="line">492</span><br><span class="line">493</span><br><span class="line">494</span><br><span class="line">495</span><br><span class="line">496</span><br><span class="line">497</span><br><span class="line">498</span><br><span class="line">499</span><br><span class="line">500</span><br><span class="line">501</span><br><span class="line">502</span><br><span class="line">503</span><br><span class="line">504</span><br><span class="line">505</span><br><span class="line">506</span><br><span class="line">507</span><br><span class="line">508</span><br><span class="line">509</span><br><span class="line">510</span><br><span class="line">511</span><br><span class="line">512</span><br><span class="line">513</span><br><span class="line">514</span><br><span class="line">515</span><br><span class="line">516</span><br><span class="line">517</span><br><span class="line">518</span><br><span class="line">519</span><br><span class="line">520</span><br><span class="line">521</span><br><span class="line">522</span><br><span class="line">523</span><br><span class="line">524</span><br><span class="line">525</span><br><span class="line">526</span><br><span class="line">527</span><br><span class="line">528</span><br><span class="line">529</span><br><span class="line">530</span><br><span class="line">531</span><br><span class="line">532</span><br><span class="line">533</span><br><span class="line">534</span><br><span class="line">535</span><br><span class="line">536</span><br><span class="line">537</span><br><span class="line">538</span><br><span class="line">539</span><br><span class="line">540</span><br><span class="line">541</span><br><span class="line">542</span><br><span class="line">543</span><br><span class="line">544</span><br><span class="line">545</span><br><span class="line">546</span><br><span class="line">547</span><br><span class="line">548</span><br><span class="line">549</span><br><span class="line">550</span><br><span class="line">551</span><br><span class="line">552</span><br><span class="line">553</span><br><span class="line">554</span><br><span class="line">555</span><br><span class="line">556</span><br><span class="line">557</span><br><span class="line">558</span><br><span class="line">559</span><br><span class="line">560</span><br><span class="line">561</span><br><span class="line">562</span><br><span class="line">563</span><br><span class="line">564</span><br><span class="line">565</span><br><span class="line">566</span><br><span class="line">567</span><br><span class="line">568</span><br><span class="line">569</span><br><span class="line">570</span><br><span class="line">571</span><br><span class="line">572</span><br><span class="line">573</span><br><span class="line">574</span><br><span class="line">575</span><br><span class="line">576</span><br><span class="line">577</span><br><span class="line">578</span><br><span class="line">579</span><br><span class="line">580</span><br><span class="line">581</span><br><span class="line">582</span><br><span class="line">583</span><br><span class="line">584</span><br><span class="line">585</span><br><span class="line">586</span><br><span class="line">587</span><br><span class="line">588</span><br><span class="line">589</span><br><span class="line">590</span><br><span class="line">591</span><br><span class="line">592</span><br><span class="line">593</span><br><span class="line">594</span><br><span class="line">595</span><br><span class="line">596</span><br><span class="line">597</span><br><span class="line">598</span><br><span class="line">599</span><br><span class="line">600</span><br><span class="line">601</span><br><span class="line">602</span><br><span class="line">603</span><br><span class="line">604</span><br><span class="line">605</span><br><span class="line">606</span><br><span class="line">607</span><br><span class="line">608</span><br><span class="line">609</span><br><span class="line">610</span><br><span class="line">611</span><br><span class="line">612</span><br><span class="line">613</span><br><span class="line">614</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> dataStructure.tree;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.NoSuchElementException;</span><br><span class="line"><span class="keyword">import</span> java.util.Stack;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> masuo</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@data</span> 2021/9/29 10:07</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@Description</span> 动态二叉树--提供构建二叉树的结构，再增加数据时自动构建二叉树</span></span><br><span class="line"><span class="comment"> * 平衡方法参考：https://zhuanlan.zhihu.com/p/165939383</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">DynamicBinaryTree</span>&lt;<span class="title">E</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//树根</span></span><br><span class="line">    <span class="keyword">transient</span> Node&lt;E&gt; root;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//修改次数</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> modCount;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//节点个数</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">int</span> size;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//是否被修改</span></span><br><span class="line">    <span class="keyword">transient</span> <span class="keyword">boolean</span> modFlag;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/****************外部接口****************/</span></span><br><span class="line">    <span class="comment">//构造函数</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">DynamicBinaryTree</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.modFlag = <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//增加节点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">add</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) &#123;</span><br><span class="line">            root = <span class="keyword">new</span> Node&lt;&gt;(item, <span class="number">1</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//调用</span></span><br><span class="line">            add(root, item);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//修改次数+1</span></span><br><span class="line">        ++modCount;</span><br><span class="line">        ++size;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//获取树高</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getDepth</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> root == <span class="keyword">null</span> ? <span class="number">0</span> : root.depth;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//查找节点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Node&lt;E&gt; <span class="title">get</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> findN(item);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//删除节点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">del</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//先判断是否存在该节点</span></span><br><span class="line">        <span class="keyword">if</span> (!checkNode(findN(item))) &#123;</span><br><span class="line">            <span class="keyword">throw</span> <span class="keyword">new</span> NoSuchElementException(<span class="string">&quot;item = &quot;</span> + item);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//存在则继续下面的步骤，由于需要递归删除，我们再次采用这个方法</span></span><br><span class="line">        <span class="comment">//删除节点时需要将所有经过的点都判断是否失衡</span></span><br><span class="line">        Stack&lt;Node&lt;E&gt;&gt; nodes = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">        del(root, item, nodes, <span class="keyword">null</span>);</span><br><span class="line">        <span class="comment">//删除之后，可以在递归时处理，也可以将经过的节点入栈，循环处理。</span></span><br><span class="line">        <span class="comment">//这里我们选择将其入栈，之后循环处理栈中的节点,栈中第一个节点必是真正删除的节点的父节点</span></span><br><span class="line">        <span class="keyword">if</span> (nodes.size() &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="comment">//处理删除时经过的节点</span></span><br><span class="line">            reBalance(nodes);</span><br><span class="line">        &#125;</span><br><span class="line">        --size;</span><br><span class="line">        ++modCount;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/****************内部接口****************/</span></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 私有增加节点函数</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 待增加节点的某一个上层节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> item 待增加节点的值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 增加后的节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node&lt;E&gt; <span class="title">add</span><span class="params">(Node&lt;E&gt; node, E item)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> Node&lt;&gt;(item, <span class="number">1</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (item.hashCode() &lt; node.item.hashCode()) &#123;</span><br><span class="line">            <span class="comment">//插入左</span></span><br><span class="line">            node.leftSon = add(node.leftSon, item);</span><br><span class="line">            <span class="keyword">if</span> (node.leftSon.parent == <span class="keyword">null</span>) &#123;</span><br><span class="line">                node.leftSon.parent = node;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//插入右</span></span><br><span class="line">            node.rightSon = add(node.rightSon, item);</span><br><span class="line">            <span class="keyword">if</span> (node.rightSon.parent == <span class="keyword">null</span>) &#123;</span><br><span class="line">                node.rightSon.parent = node;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//判断平衡，计算高度，计算平衡因子</span></span><br><span class="line">        <span class="keyword">int</span> left = node.leftSon == <span class="keyword">null</span> ? <span class="number">0</span> : node.leftSon.depth;</span><br><span class="line">        <span class="keyword">int</span> right = node.rightSon == <span class="keyword">null</span> ? <span class="number">0</span> : node.rightSon.depth;</span><br><span class="line">        node.depth = Math.max(left, right) + <span class="number">1</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> bf = left - right;<span class="comment">//平衡因子</span></span><br><span class="line">        <span class="keyword">if</span> (Math.abs(bf) &gt; <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="comment">//不平衡，需要旋转</span></span><br><span class="line">            node = rotate(node, item);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 添加节点时，失衡旋转方法I</span></span><br><span class="line"><span class="comment">     * 此方法只适合在添加节点时使用，可节省一定的时间，因为在插入节点时，</span></span><br><span class="line"><span class="comment">     * 我们知道插入节点得值，所以我们直接使用该值来判断旋转方方向</span></span><br><span class="line"><span class="comment">     * 从失衡节点往下寻找插入节点，只找前两步即可，前两步即可确定旋转方式</span></span><br><span class="line"><span class="comment">     * 需要根据item的值来判断前两步的方向</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 失衡节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> item 插入节点的值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 调整后的节点的根节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node&lt;E&gt; <span class="title">rotate</span><span class="params">(Node&lt;E&gt; node, E item)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//先找插入节点</span></span><br><span class="line">        Node&lt;E&gt; temp = node;</span><br><span class="line">        StringBuilder RL = <span class="keyword">new</span> StringBuilder();</span><br><span class="line">        <span class="keyword">while</span> (RL.length() &lt; <span class="number">2</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (item.hashCode() &lt; temp.item.hashCode()) &#123;</span><br><span class="line">                <span class="comment">//左高</span></span><br><span class="line">                RL.append(<span class="string">&quot;L&quot;</span>);</span><br><span class="line">                temp = temp.leftSon;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//右高</span></span><br><span class="line">                RL.append(<span class="string">&quot;R&quot;</span>);</span><br><span class="line">                temp = temp.rightSon;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//System.out.println(size);</span></span><br><span class="line">        <span class="comment">//更新高度</span></span><br><span class="line">        <span class="comment">//node.depth = reSetDepth(node);</span></span><br><span class="line">        <span class="keyword">return</span> rotate(node, RL.toString());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 删除节点时，失衡节点旋转方法II</span></span><br><span class="line"><span class="comment">     * 与第一种方法不一样的是这种方法通过判断节点的平衡因子来判断旋转方向</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 失衡节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">rotate</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//根据平衡因子判断旋转方式</span></span><br><span class="line">        Node&lt;E&gt; temp = node;</span><br><span class="line">        StringBuilder RL = <span class="keyword">new</span> StringBuilder();</span><br><span class="line">        <span class="keyword">while</span> (RL.length() &lt; <span class="number">2</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (getBF(temp) &gt; <span class="number">0</span>) &#123;</span><br><span class="line">                RL.append(<span class="string">&quot;R&quot;</span>);</span><br><span class="line">                temp = temp.leftSon;</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (getBF(temp) &lt; <span class="number">0</span>) &#123;</span><br><span class="line">                RL.append(<span class="string">&quot;L&quot;</span>);</span><br><span class="line">                temp = temp.rightSon;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        rotate(node, RL.toString());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 具体旋转方法</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 旋转时以node为固定节点进行旋转</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> RL   左右    所有的旋转，不管是LL、RR、LR、RL，都可以拆分为R，或者L旋转</span></span><br><span class="line"><span class="comment">     *             需要注意的是，在我这里的L代表的是左高，R代表的是右高，</span></span><br><span class="line"><span class="comment">     *             即树倾斜方向，不是旋转的方向，旋转方向与倾斜方向相反</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 调整后的node节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node&lt;E&gt; <span class="title">rotate</span><span class="params">(Node&lt;E&gt; node, String RL)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">switch</span> (RL) &#123;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&quot;LL&quot;</span>:</span><br><span class="line">                <span class="comment">//单旋，左高，需顺时针旋转</span></span><br><span class="line">                node = L_rotate(node);</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&quot;RR&quot;</span>:</span><br><span class="line">                node = R_rotate(node);</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&quot;LR&quot;</span>:</span><br><span class="line">                <span class="comment">//先左旋，在右旋</span></span><br><span class="line">                <span class="comment">//注意此时需要先调整插入节点与其父节点，让其变成单旋</span></span><br><span class="line">                node.leftSon = R_rotate(node.leftSon);</span><br><span class="line">                node = L_rotate(node);</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="string">&quot;RL&quot;</span>:</span><br><span class="line">                <span class="comment">//先右旋，在左旋</span></span><br><span class="line">                node.rightSon = L_rotate(node.rightSon);</span><br><span class="line">                node = R_rotate(node);</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//这个R代表右侧高，右侧高需左旋，左单旋</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node&lt;E&gt; <span class="title">R_rotate</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//Node&lt;E&gt; A = node;</span></span><br><span class="line">        Node&lt;E&gt; B = node.rightSon;</span><br><span class="line">        Node&lt;E&gt; Bl = B.leftSon;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (Bl != <span class="keyword">null</span>) &#123;</span><br><span class="line">            Bl.parent = node;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//node的父节点</span></span><br><span class="line">        B.parent = node.parent;</span><br><span class="line">        <span class="keyword">if</span> (root == node) &#123;</span><br><span class="line">            root = B;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> (node.isLeftChild()) &#123;</span><br><span class="line">                node.parent.leftSon = B;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                node.parent.rightSon = B;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        B.leftSon = node;</span><br><span class="line">        node.parent = B;</span><br><span class="line">        node.rightSon = Bl;</span><br><span class="line"></span><br><span class="line">        resetDepth(node);</span><br><span class="line">        resetDepth(B);</span><br><span class="line">        <span class="keyword">return</span> B;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//这个 右单旋</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node&lt;E&gt; <span class="title">L_rotate</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//Node&lt;E&gt; B = node;</span></span><br><span class="line">        Node&lt;E&gt; A = node.leftSon;</span><br><span class="line">        Node&lt;E&gt; Ar = A.rightSon;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (Ar != <span class="keyword">null</span>) &#123;</span><br><span class="line">            Ar.parent = node;</span><br><span class="line">        &#125;</span><br><span class="line">        A.parent = node.parent;</span><br><span class="line">        <span class="keyword">if</span> (root == node) &#123;</span><br><span class="line">            root = A;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> (node.isLeftChild()) &#123;</span><br><span class="line">                node.parent.leftSon = A;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                node.parent.rightSon = A;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        A.rightSon = node;</span><br><span class="line">        node.parent = A;</span><br><span class="line">        node.leftSon = Ar;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//重置高度，只需调整高度变化得节点</span></span><br><span class="line">        resetDepth(node);</span><br><span class="line">        resetDepth(A);</span><br><span class="line">        <span class="keyword">return</span> A;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 旋转时，高度改变的只有两个节点，其余节点高度不变，利用这一特性</span></span><br><span class="line"><span class="comment">     * 我们只需在旋转后根据其子节点高度的最大值就能获得其高度</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 旋转后的根节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">resetDepth</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">int</span> left = node.leftSon == <span class="keyword">null</span> ? <span class="number">0</span> : node.leftSon.depth;</span><br><span class="line">            <span class="keyword">int</span> right = node.rightSon == <span class="keyword">null</span> ? <span class="number">0</span> : node.rightSon.depth;</span><br><span class="line">            <span class="keyword">int</span> depth = Math.max(left, right) + <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">if</span> (node.depth != depth) &#123;</span><br><span class="line">                node.depth = depth;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 私有查询节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> item 节点值</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> Node&lt;E&gt; <span class="title">findN</span><span class="params">(E item)</span> </span>&#123;</span><br><span class="line">        Node&lt;E&gt; temp = root;</span><br><span class="line">        <span class="keyword">while</span> (temp != <span class="keyword">null</span> &amp;&amp; temp.item != item) &#123;</span><br><span class="line">            <span class="keyword">if</span> (item.hashCode() &lt; temp.item.hashCode()) &#123;</span><br><span class="line">                <span class="comment">//在左侧找</span></span><br><span class="line">                temp = temp.leftSon;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//在右侧找</span></span><br><span class="line">                temp = temp.rightSon;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> temp;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 处理经过的节点</span></span><br><span class="line"><span class="comment">     * 调整父节点高度</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> nodes 删除经过的节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">reBalance</span><span class="params">(Stack&lt;Node&lt;E&gt;&gt; nodes)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">do</span> &#123;</span><br><span class="line">            Node&lt;E&gt; temp = nodes.pop();<span class="comment">//真正删除的节点的父节点,其高度可能没有发生改变</span></span><br><span class="line">            <span class="comment">//调整高度</span></span><br><span class="line">            resetDepth(temp);</span><br><span class="line"></span><br><span class="line">            <span class="comment">//判断平衡因子</span></span><br><span class="line">            <span class="keyword">if</span> (Math.abs(getBF(temp)) &gt; <span class="number">1</span>) &#123;</span><br><span class="line">                <span class="comment">//不平衡，需要旋转</span></span><br><span class="line">                rotate(temp);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">while</span> (!nodes.empty());</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 删除某一结点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 删除节点所在的树的某一结点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> item 删除节点的值</span></span><br><span class="line"><span class="comment">     *             左子树存在：则使用删除节点的左子树的最大值替换待删除结点 *</span></span><br><span class="line"><span class="comment">     *             右子树存在：则使用删除节点的右子树的最小值替换待删除节点</span></span><br><span class="line"><span class="comment">     *             左右子树都为空：父节点的子节点为空</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">del</span><span class="params">(Node&lt;E&gt; node, E item, Stack&lt;Node&lt;E&gt;&gt; nodes, String LR)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node.item != item) &#123;</span><br><span class="line">            <span class="comment">//这个不是待删除节点</span></span><br><span class="line">            nodes.add(node);</span><br><span class="line">            <span class="keyword">if</span> (item.hashCode() &lt; node.item.hashCode()) &#123;</span><br><span class="line">                <span class="comment">//待删除节点位与此节点的左侧</span></span><br><span class="line">                del(node.leftSon, item, nodes, <span class="string">&quot;L&quot;</span>);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//待删除节点位于此节点的右侧</span></span><br><span class="line">                del(node.rightSon, item, nodes, <span class="string">&quot;R&quot;</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//是待删除节点</span></span><br><span class="line">            <span class="comment">//1. 没有子节点，叶子节点直接删除，从删除节点向上调整平衡</span></span><br><span class="line">            <span class="comment">//2. 有一个子节点，则用子节点直接替代该节点</span></span><br><span class="line">            <span class="comment">//3. 有两个子节点，当有两个子节点的时候，有多种删除方法，</span></span><br><span class="line">            <span class="comment">//   3.1、使用待删除节点的左子树的最大值，最好为叶子节点</span></span><br><span class="line">            <span class="comment">//   3.2、使用待删除节点的右子树的最小值，最好为叶子节点</span></span><br><span class="line">            <span class="comment">//   3.3、使用待删除节点左右子树中较高的子树，且满足上面相应的条件</span></span><br><span class="line">            <span class="keyword">if</span> (node.leftSon == <span class="keyword">null</span> &amp;&amp; node.rightSon == <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="comment">//没有子节点，叶子节点直接删除（根节点也是）</span></span><br><span class="line">                delWithOutSon(node, LR);</span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (node.rightSon != <span class="keyword">null</span> &amp;&amp; node.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="comment">//左右子树都不为空,有两个子节点，</span></span><br><span class="line">                delWithTwoSon(node, nodes);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//左右有一个为空</span></span><br><span class="line">                delWithOneSon(node, LR);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 待删除节点有两个子节点</span></span><br><span class="line"><span class="comment">     * 删除有两个子节点的节点可以选择让他的【前驱】或【后继】来代替它</span></span><br><span class="line"><span class="comment">     * 在这里我们选择从左侧选择待删除节点的前驱进行删除，</span></span><br><span class="line"><span class="comment">     * 参考自旧金山大学计算机科学与技术学院--https://myusf.usfca.edu/arts-sciences/computer-science</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> delNode 待删除节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> nodes   经过的结点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">delWithTwoSon</span><span class="params">(Node&lt;E&gt; delNode, Stack&lt;Node&lt;E&gt;&gt; nodes)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//需要找到左子树的最大值</span></span><br><span class="line">        nodes.add(delNode);</span><br><span class="line">        <span class="comment">//待删除结点的左子树</span></span><br><span class="line">        Node&lt;E&gt; temp = delNode.leftSon;<span class="comment">//因为有两个子节点，所以左子节点必不为空</span></span><br><span class="line">        <span class="comment">//先找左子树上的最大值，因为二叉树的特性，所以从右子树寻找</span></span><br><span class="line">        <span class="keyword">while</span> (temp.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            nodes.add(temp);</span><br><span class="line">            temp = temp.rightSon;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//找到最大值之后，替换del的item</span></span><br><span class="line">        delNode.item = temp.item;</span><br><span class="line">        <span class="comment">//替换节点值之后删除最大值节点，此处，最大值节点有以下情况</span></span><br><span class="line">        <span class="comment">//1。最大节点为叶子节点</span></span><br><span class="line">        <span class="comment">//2。最大节点为非叶子节点，此时最大节点只有左子树（可能为空），无右子树</span></span><br><span class="line"></span><br><span class="line">        <span class="comment">//判断最大值节点是否是叶子节点，</span></span><br><span class="line">        <span class="keyword">if</span> (isLeaf(temp)) &#123;</span><br><span class="line">            <span class="comment">//是叶子节点，则直接删除该节点，父节点高度不一定改变</span></span><br><span class="line">            delLeaf(temp, (temp.parent.leftSon == temp) ? <span class="string">&quot;L&quot;</span> : <span class="string">&quot;R&quot;</span>);</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//不是叶子节点，则将该节点的左子树放到其父节点的左子树上，父节点高度不一定改变</span></span><br><span class="line">            temp.parent.leftSon = temp.leftSon;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 待删除节点有一个子节点，删除并更新父节点高度</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> delNode 待删除节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> lr      待删除节点是父节点的左儿子还是右儿子</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">delWithOneSon</span><span class="params">(Node&lt;E&gt; delNode, String lr)</span> </span>&#123;</span><br><span class="line">        Node&lt;E&gt; node = delNode.rightSon == <span class="keyword">null</span> ? delNode.leftSon : delNode.rightSon;</span><br><span class="line">        <span class="keyword">if</span> (lr == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="comment">//lr为空说明待删除节点为根节点</span></span><br><span class="line">            root = node;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">if</span> (lr.equals(<span class="string">&quot;L&quot;</span>)) &#123;</span><br><span class="line">                delNode.parent.leftSon = node;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                delNode.parent.rightSon = node;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//因为只有一个子节点，所以父节点的高度需要降低1</span></span><br><span class="line">            --delNode.parent.depth;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 待删除节点无子树,即叶子节点，删除并更新父节点高度</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> delNode 待删除节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> lr      待删除节点是父节点的左儿子还是右儿子</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">delWithOutSon</span><span class="params">(Node&lt;E&gt; delNode, String lr)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (lr == <span class="keyword">null</span>) root = <span class="keyword">null</span>;</span><br><span class="line">            <span class="comment">//lr为空说明没有父节点，即为根节点，删除根结点所以将根节点设置为空</span></span><br><span class="line">        <span class="keyword">else</span> delLeaf(delNode, lr);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 删除叶子节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> temp 待删除的叶子节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">delLeaf</span><span class="params">(Node&lt;E&gt; temp, String lr)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (lr.equals(<span class="string">&quot;L&quot;</span>)) &#123;</span><br><span class="line">            <span class="comment">//待删除节点为左子树</span></span><br><span class="line">            temp.parent.leftSon = <span class="keyword">null</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">//待删除节点为右子树</span></span><br><span class="line">            temp.parent.rightSon = <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 是否叶子节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> temp 待判断节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> true/false</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">isLeaf</span><span class="params">(Node&lt;E&gt; temp)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> temp.leftSon == <span class="keyword">null</span> &amp;&amp; temp.rightSon == <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 计算平衡因子</span></span><br><span class="line"><span class="comment">     * 左高 - 右高</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> int 平衡因子 -2 -1 0 1 2</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getBF</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//判断平衡，计算高度，计算平衡因子</span></span><br><span class="line">        <span class="keyword">int</span> left = node.leftSon == <span class="keyword">null</span> ? <span class="number">0</span> : node.leftSon.depth;</span><br><span class="line">        <span class="keyword">int</span> right = node.rightSon == <span class="keyword">null</span> ? <span class="number">0</span> : node.rightSon.depth;</span><br><span class="line">        <span class="keyword">return</span> left - right;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 获取自 node 结点开始的最大的节点</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 开始节点</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 最大节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> Node&lt;E&gt; <span class="title">getMaxLeaf</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//根据二叉查找树的特点，大的都在节点右侧</span></span><br><span class="line">        <span class="comment">//首先判断右子树是否为空</span></span><br><span class="line">        <span class="keyword">while</span> (node.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            node = node.rightSon;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//右子树为空则返回node本身</span></span><br><span class="line">        <span class="keyword">return</span> node;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 检查节点是否存在</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> temp 待检查节点</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">checkNode</span><span class="params">(Node&lt;E&gt; temp)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> temp != <span class="keyword">null</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/****************废弃****************/</span></span><br><span class="line">    <span class="meta">@Deprecated</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">calDepth</span><span class="params">(Node&lt;E&gt; n)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (n == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (n.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            left = calDepth(n.leftSon);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (n.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            right = calDepth(n.rightSon);</span><br><span class="line">        &#125;</span><br><span class="line">        n.depth = Math.max(left, right) + <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">return</span> n.depth;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 重置 节点高度</span></span><br><span class="line"><span class="comment">     * 由旋转后调整变化节点代替</span></span><br><span class="line"><span class="comment">     *</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> node 自该节点往下重置高度</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 节点高度</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="meta">@Deprecated</span></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">int</span> <span class="title">reSetDepth</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//递归</span></span><br><span class="line">        <span class="keyword">if</span> (node == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//判断平衡，计算高度，计算平衡因子</span></span><br><span class="line">        <span class="keyword">int</span> leftH = node.leftSon == <span class="keyword">null</span> ? <span class="number">0</span> : reSetDepth(node.leftSon);</span><br><span class="line">        <span class="keyword">int</span> rightH = node.rightSon == <span class="keyword">null</span> ? <span class="number">0</span> : reSetDepth(node.rightSon);</span><br><span class="line">        <span class="keyword">if</span> (node.leftSon != <span class="keyword">null</span>) node.leftSon.depth = leftH;</span><br><span class="line">        <span class="keyword">if</span> (node.rightSon != <span class="keyword">null</span>) node.rightSon.depth = rightH;</span><br><span class="line">        <span class="keyword">return</span> Math.max(leftH, rightH) + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/****************遍历****************/</span></span><br><span class="line">    <span class="comment">//前序遍历</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">preList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        System.out.print(<span class="string">&quot;前序遍历：&quot;</span>);</span><br><span class="line">        <span class="keyword">this</span>.preList(root);</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">preList</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">            System.out.print(node.item + <span class="string">&quot;  &quot;</span>);</span><br><span class="line">            <span class="keyword">if</span> (node.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">                preList(node.leftSon);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (node.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">                preList(node.rightSon);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//中序遍历</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">midList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        System.out.print(<span class="string">&quot;中序遍历：&quot;</span>);</span><br><span class="line">        <span class="keyword">this</span>.midList(root);</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">midList</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">if</span> (node.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">                tailList(node.leftSon);</span><br><span class="line">            &#125;</span><br><span class="line">            System.out.print(node.item + <span class="string">&quot;  &quot;</span>);</span><br><span class="line">            <span class="keyword">if</span> (node.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">                tailList(node.rightSon);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//后序遍历</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">tailList</span><span class="params">()</span> </span>&#123;</span><br><span class="line">        System.out.print(<span class="string">&quot;后序遍历：&quot;</span>);</span><br><span class="line">        <span class="keyword">this</span>.tailList(root);</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">tailList</span><span class="params">(Node&lt;E&gt; node)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (node.leftSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            tailList(node.leftSon);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (node.rightSon != <span class="keyword">null</span>) &#123;</span><br><span class="line">            tailList(node.rightSon);</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.print(node.item + <span class="string">&quot;  &quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">//二叉树节点</span></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">E</span>&gt; <span class="keyword">implements</span> <span class="title">Cloneable</span> </span>&#123;</span><br><span class="line">        <span class="keyword">transient</span> E item;</span><br><span class="line">        <span class="keyword">int</span> depth;<span class="comment">//计算Balance Factor 平衡因子</span></span><br><span class="line">        Node&lt;E&gt; parent;</span><br><span class="line">        Node&lt;E&gt; leftSon;</span><br><span class="line">        Node&lt;E&gt; rightSon;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(E item, <span class="keyword">int</span> depth)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.item = item;</span><br><span class="line">            <span class="keyword">this</span>.depth = depth;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(E item, Node&lt;E&gt; leftSon, Node&lt;E&gt; rightSon, Node&lt;E&gt; parent)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.item = item;</span><br><span class="line">            <span class="keyword">this</span>.leftSon = leftSon;</span><br><span class="line">            <span class="keyword">this</span>.rightSon = rightSon;</span><br><span class="line">            <span class="keyword">this</span>.parent = parent;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isLeftChild</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">if</span> (<span class="keyword">this</span>.parent == <span class="keyword">null</span>) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">this</span>.parent.leftSon == <span class="keyword">this</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h4 id="霍夫曼树"><a href="#霍夫曼树" class="headerlink" title="霍夫曼树"></a>霍夫曼树</h4><blockquote>
<p>霍夫曼树是二叉树的一种特殊形式，又称为最优二叉树，其主要作用在于数据压缩和编码长度的优化。</p>
</blockquote>
<h5 id="实现-3"><a href="#实现-3" class="headerlink" title="实现"></a>实现</h5><h5 id="应用"><a href="#应用" class="headerlink" title="应用"></a>应用</h5><p>参考：<a target="_blank" rel="noopener" href="https://www.jianshu.com/p/5ad3e97d54a3">https://www.jianshu.com/p/5ad3e97d54a3</a></p>
<h4 id="2-3-4树"><a href="#2-3-4树" class="headerlink" title="2-3-4树"></a>2-3-4树</h4><blockquote>
<p>2-3-4树是</p>
</blockquote>
<p>实现</p>
<h4 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h4><blockquote>
<p>红黑树是一种自平衡的二叉查找树，是一种高效的查找树。</p>
</blockquote>
<h5 id="实现-4"><a href="#实现-4" class="headerlink" title="实现"></a>实现</h5><p>参考：<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/91960960">https://zhuanlan.zhihu.com/p/91960960</a></p>
<h4 id="B树"><a href="#B树" class="headerlink" title="B树"></a>B树</h4><blockquote>
<p>B树又叫B-树、B树，是一种平衡的多路查找树，注意： <strong>B树就是B-树，”-“是个连字符号，不是减号</strong> 。</p>
<p>B 树多用于数据库索引。可以认为是m叉的多路平衡查找树。</p>
<p>为什么使用B树，因为我们需要考虑磁盘IO的影响，一次IO，写入大量数据要比每条数据都进行IO要快。</p>
<p>数据库索引是存储在磁盘上的，当数据量很大时，就不能把整个索引全部加载到内存了，只能逐一加载每个磁盘页，磁盘页就是索引树（B树）的节点，所以我们需要减少IO的次数。</p>
<p>B树的特征是 <strong>矮胖</strong> ，它的每个节点最多包含m个子树，m称为B树的阶，m的大小取决于磁盘页的大小</p>
</blockquote>
<h5 id="特性"><a href="#特性" class="headerlink" title="特性"></a>特性</h5><p>在了解B树之前先来了解一下如下概念</p>
<ul>
<li>阶数：一个节点最多可以有几个子节点（多用m表示）</li>
<li>度：一个节点已有的子节点数</li>
<li>关键字：节点上的数值</li>
</ul>
<p>B树满足以下条件</p>
<ul>
<li><p>根节点至少有两个子节点（？，这里大家可能会有个疑惑，为什么根节点至少有两个子节点，可以看下图插入时的B树构造）</p>
</li>
<li><p>所有的叶子节点都在同一层</p>
</li>
<li><p>每个非根节点所包含的关键字数n满足：<br>  $$<br>  m/2-1 &lt;= n &lt;= m-1<br>  $$</p>
</li>
<li><p>有k个关键字的非叶子节点有k+1个孩子</p>
</li>
</ul>
<p>如下：3阶的B树</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121094758.png" alt="image-20220121094757951"></p>
<p>一个3阶B树（key1&lt;key2&lt;key3&lt;key4&lt;key5）</p>
<p>含有1个关键字的构造，这里，子树为空，暂不显示</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121102526.png" alt="image-20220121102526696"></p>
<p>含有2个关键字的构造</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121102541.png" alt="image-20220121102540923"></p>
<p>再插入时会发生分裂</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121102632.png" alt="image-20220121102632543"></p>
<p>第四次插入</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121103417.png" alt="image-20220121103417213"></p>
<p>第五次插入</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121103528.png" alt="image-20220121103527914"></p>
<p>可以看到，叶子节点都在同一层</p>
<h5 id="应用-1"><a href="#应用-1" class="headerlink" title="应用"></a>应用</h5><blockquote>
<p> 数据库</p>
</blockquote>
<h5 id="实现-5"><a href="#实现-5" class="headerlink" title="实现"></a>实现</h5><p>参考：<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/146252512">https://zhuanlan.zhihu.com/p/146252512</a></p>
<h4 id="B-树"><a href="#B-树" class="headerlink" title="B+树"></a>B+树</h4><blockquote>
<p>B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间（节点关键字不在存储数据，只存储索引），让查询速度更加稳定，其速度完全接近于二分法查找。</p>
</blockquote>
<p>B+树特点</p>
<ul>
<li><p>每个节点至多有m个子树</p>
</li>
<li><p>非根节点关键字个数n满足：<br>  $$<br>  m/2 &lt;= n &lt;= m-1<br>  $$</p>
</li>
<li><p>相邻的叶子节点通过指针连接起来，且是有序的。</p>
</li>
</ul>
<p>前两次插入跟B树是一样的，所以直接看第三次插入</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121105644.png" alt="image-20220121105644838"></p>
<p>第四次插入</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121105706.png" alt="image-20220121105706229"></p>
<h5 id="实现-6"><a href="#实现-6" class="headerlink" title="实现"></a>实现</h5><p>第五次插入</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220121105733.png" alt="image-20220121105733048"></p>
<h5 id="B与B-的不同"><a href="#B与B-的不同" class="headerlink" title="B与B+的不同"></a>B与B+的不同</h5><ul>
<li>B树非叶子节点存储数据，B+树非叶子节点不存储数据</li>
<li>B+树叶子节点是用链表相连的</li>
<li>B树中关键字只会出现一次，但是B+树会出现多次。</li>
</ul>
<h5 id="实现-7"><a href="#实现-7" class="headerlink" title="实现"></a>实现</h5><p>参考：<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/146252512">https://zhuanlan.zhihu.com/p/146252512</a></p>
<h4 id="B-树-1"><a href="#B-树-1" class="headerlink" title="B*树"></a>B*树</h4><blockquote>
<p>B*树是B+树的变种，相对于B+树他们的不同之处如下：</p>
<p>（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b<em>树的初始化个数为（cei(2/3</em>m)）</p>
<p>（2）B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；</p>
</blockquote>
<h5 id="实现-8"><a href="#实现-8" class="headerlink" title="实现"></a>实现</h5><p>参考：<a target="_blank" rel="noopener" href="https://zhuanlan.zhihu.com/p/146252512">https://zhuanlan.zhihu.com/p/146252512</a></p>
<h2 id="图（map）"><a href="#图（map）" class="headerlink" title="图（map）"></a><strong>图</strong>（map）</h2><h2 id="散列表（hash）"><a href="#散列表（hash）" class="headerlink" title="散列表（hash）"></a><strong>散列表</strong>（hash）</h2><h1 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h1><p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20211124093637.png" alt="img"></p>
<h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><blockquote>
<p>循环相邻比较，交换</p>
<p>依次对两个数比较大小，较大的数冒起来，较小的数压下来</p>
<p>排序<strong>稳定</strong>，但速度<strong>慢</strong>。</p>
</blockquote>
<h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><blockquote>
<p>针对冒泡排序的优化，一遍循环只选择最大或最小的，交换</p>
<p>比冒泡快一些，但代价是跳跃性交换，排序<strong>不稳定</strong>。</p>
</blockquote>
<h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><blockquote>
<p>将第一个数据作为已排序数组，其余数据插入数组中</p>
<p>扑克牌排序</p>
</blockquote>
<h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><blockquote>
<p>插入排序的优化，分步长插入排序</p>
</blockquote>
<h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><blockquote>
<p>寻找基准值，与基准值作比较，大的放一侧，小的放另一侧，如此循环</p>
<p>分治思想</p>
<p>对于小规模数据（n&lt;100），快排由于用了递归，其效率可能还不如插排。因此通常可以定义一个阈值，当递归的数据量很小时停止递归，直接调用插排。</p>
</blockquote>
<h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><blockquote>
<p>两两对比，合并有序数组</p>
</blockquote>
<h2 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h2><blockquote>
<p>基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。</p>
</blockquote>
<h2 id="桶排序"><a href="#桶排序" class="headerlink" title="桶排序"></a>桶排序</h2><blockquote>
<p>将</p>
</blockquote>
<h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><blockquote>
<p>二分法，</p>
<p>将待排数组构建成一个最大堆，将堆顶最大元素换到后面，然后堆容量减1；类似进行N-1次操作即可。</p>
</blockquote>
<h2 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h2><blockquote>
<p>计数排序适用于<strong>大量重复</strong>数据，数据集中在一个区间内，找出最大值最小值，取其为下标区间。</p>
<p>比如统计年龄</p>
</blockquote>
<h1 id="算法"><a href="#算法" class="headerlink" title="算法"></a>算法</h1><h2 id="KMP算法"><a href="#KMP算法" class="headerlink" title="KMP算法"></a>KMP算法</h2><blockquote>
<p>KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。</p>
<p>KMP算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了一定程度的提高。</p>
</blockquote>
<p>想要搞明白KMP算法，首先需要直到<strong>前缀</strong>和<strong>后缀</strong>。</p>
<h3 id="前缀"><a href="#前缀" class="headerlink" title="前缀"></a>前缀</h3><p>比如，有一个字符串<code>abbaab</code>，那么它的前缀有：a、ab、abb、abba、abbaa</p>
<h3 id="后缀"><a href="#后缀" class="headerlink" title="后缀"></a>后缀</h3><p>同上字符串，它的后缀有：b、ab、aab、baab、bbaab</p>
<h3 id="公共前后缀"><a href="#公共前后缀" class="headerlink" title="公共前后缀"></a>公共前后缀</h3><p>公共前后缀指的是在一个字符串中一个字串即是前缀也是后缀。</p>
<h3 id="前缀表"><a href="#前缀表" class="headerlink" title="前缀表"></a>前缀表</h3><p>前缀表代表的是模式串<strong>i</strong>位置及之前的字串中的<strong>最长公共前后缀</strong>（包括i位置），其作用是当i位置发生不匹配时，可以根据前缀表来回溯。</p>
<p>比如字符串<code>ababa</code>，</p>
<p>i == 0，字串为“a”，最长公共前后缀长度为0</p>
<p>i == 1，字串为“ab”，最长公共前后缀长度为0</p>
<p>i == 2，字串为“aba”，最长公共前后缀长度为1(a)</p>
<p>i == 3，字串为“abab”，最长公共前后缀长度为2(ab)</p>
<p>i == 4，字串为“ababa”，最长公共前后缀长度为3(aba)</p>
<p>但是，在很多实际应用中，前缀表（prefix）为了适应代码，出现了两种变形（next）。</p>
<p><strong>第一种</strong></p>
<p>将前缀表整体右移，第一位补<code>-1</code>.</p>
<p><strong>第二种</strong></p>
<p>将前缀表整体减一。</p>
<p>具体如下表，方式1代表初始的前缀表，方式2代表整体右移的前缀表，方式3代表整体减一的前缀表</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331111312.png" alt="image-20220331111311735"></p>
<h3 id="构建next数组"><a href="#构建next数组" class="headerlink" title="构建next数组"></a>构建next数组</h3><p>有了数组的前缀和后缀之后，我们就可以构建<strong>next数组</strong>了。根据要构建的next数组形式有不同的构建方式。</p>
<p>推荐：<a target="_blank" rel="noopener" href="https://www.bilibili.com/video/BV1UL411E7M8/?spm_id_from=333.788.recommend_more_video.3">https://www.bilibili.com/video/BV1UL411E7M8/?spm_id_from=333.788.recommend_more_video.3</a></p>
<h4 id="方式1"><a href="#方式1" class="headerlink" title="方式1"></a>方式1</h4><p>这种求出来的数组被叫做前缀表（prefix），也可以用作next，看个人习惯。</p>
<p>在该方法中next数组的含义是**{0，i}区间的字符串的最长公共前后缀**。</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331114357.png" alt="image-20220330164334731"></p>
<p>求前缀和的过程（本人的思考过程）</p>
<p>在以下过程中**next[i]<strong>数组代表的是i位置上的最长前后缀长度，</strong>str[]**数组代表模式串转换成的字符数组。</p>
<p>由于在 <code>i = 0</code> 时，子串只有一个字符，前后缀都为空，所以规定<code>next[0] = 0</code>。</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331143949.png" alt="image-20220331143949616"></p>
<p>在求next数组时，我们需要比较子串的前缀和后缀，然后给数组的当前位置赋值，给数组赋值，我们只需要找个变量循环即可，但是<strong>如何比较子串的前缀和后缀</strong>是我们需要解决的问题。</p>
<p><strong>比较字串的前缀和后缀</strong></p>
<p>子串区间：【0，i】，</p>
<p>由上可知，前缀必定以str[0]开头，后缀必定以str[i]结束，且next[i-1]代表的是<strong>【0，i-1】</strong>区间的最长公共前后缀长度。next[i-1]的取值又有两种情况。</p>
<p><strong>情况1</strong>：如果<code>next[i-1] &gt; 0</code>则说明<strong>【0，i - 1】</strong>区间有公共的前后缀，我们设定<strong>preLen</strong>代表**next[i-1]**。</p>
<p>str[preLen]即可代表【0，preLen】区间最长公共前后缀的前缀的下一个字符。</p>
<blockquote>
<p>举个例子，模式串为 <code>abcdabca</code>，我们可以手算出其next数组为{0，0，0，0，1，2，3，1}</p>
<p>当 i=6 时，next[i-1] = next[5] = 2 = preLen，str[preLen] = str[2] = ‘c’。</p>
<p>str[preLen] 代表的就是【0，5】区间，即 <code>abcdab</code> 的最长公共前后缀（<code>ab</code>）的前缀的下一个字符。</p>
</blockquote>
<p>此时我们只需要判断str[i]和str[preLen]是否相等</p>
<ul>
<li>相等，那么<code>next[i] = next[i-1] + 1 = preLen + 1</code>。</li>
<li>不相等，那么我们需要对preLen回退，让<code>preLen = next[preLen - 1]</code>。</li>
</ul>
<blockquote>
<p><strong>为什么让preLen = next[preLen - 1]？</strong></p>
<p>举个:chestnut:</p>
<p>模式串 <code>abababc</code>，手算next[] = {0，0，1，2，3，4，0}</p>
<p>当 <code>i = 6</code>时，根据过程已经得到 <code>j = 4</code>，此时子串为 <code>ababa</code>。</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402152541.png" alt="image-20220402152541749"></p>
<p>根据图可知，回退一次之后，<code>str[i] != str[j]</code>仍然成立，</p>
<p>继续回退，此时<code>j = next[1] = 0</code>,不符合 <code>j&gt;0</code>的条件，退出循环。</p>
</blockquote>
<p><strong>情况2</strong>：如果<code>next[i-1] &lt;= 0</code>，则说明【0，i-1】区间没有公共的前后缀，此时我们只需要判断str[i]和str[preLen]是否相等</p>
<ul>
<li>相等，那么<code>next[i] = next[i-1] + 1 = preLen + 1</code></li>
<li>不相等，<code>next[i] = 0 = preLen</code>，因为preLen不会小于0，只会大于等于0。</li>
</ul>
<blockquote>
<p>至于preLen为啥不会小于0，因为在给preLen赋值时，在它等于0时就会退出</p>
</blockquote>
<p>方式1的代码如下：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] getPrefix(String pattern) &#123;</span><br><span class="line">    <span class="keyword">int</span> len = pattern.length();</span><br><span class="line">    <span class="keyword">int</span>[] prefix = <span class="keyword">new</span> <span class="keyword">int</span>[len];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>, j = <span class="number">0</span>; i &lt; len; i++) &#123;</span><br><span class="line">        <span class="comment">// i 指向next，j 指向前缀</span></span><br><span class="line">        <span class="keyword">while</span> (j &gt; <span class="number">0</span> &amp;&amp; pattern.charAt(i) != pattern.charAt(j)) &#123;</span><br><span class="line">            <span class="comment">// j 回退 ,</span></span><br><span class="line">            j = prefix[j - <span class="number">1</span>];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (pattern.charAt(i) == pattern.charAt(j)) &#123;</span><br><span class="line">            j++;</span><br><span class="line">        &#125;</span><br><span class="line">        prefix[i] = j;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> prefix;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p>一个完整的过程如下：</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220331144103.png" alt="image-20220331144103819"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402152958.png" alt="image-20220402152958547"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153014.png" alt="image-20220402153013089"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153025.png" alt="image-20220402153025156"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153037.png" alt="image-20220402153037308"></p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220402153048.png" alt="image-20220402153048454"></p>
<h4 id="方式2"><a href="#方式2" class="headerlink" title="方式2"></a>方式2</h4><blockquote>
<p>可参考：<a target="_blank" rel="noopener" href="https://juejin.cn/post/6951026793801318408">https://juejin.cn/post/6951026793801318408</a></p>
</blockquote>
<p>求方式2的<strong>next数组</strong>就是求<strong>从0到发生不匹配位置之前</strong>的<strong>模式子串</strong>的最长的<strong>公共前后缀</strong>的长度。</p>
<p><strong>注意</strong>，此时next数组的含义发生了改变，此时next数组的含义是{0,i-1}区间最长的公共前后缀的长度。</p>
<p>比如，主串为<code>ababacaacb</code>，模式串为<code>ababaa</code>。</p>
<p>第一次匹配时，发生不匹配的位置如下：</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220329171459.png" alt="image-20220329171459891"></p>
<p>此时的模式子串为：<code>ababa</code>，该字串的前缀有：a、ab、aba、abab，后缀有：a、ba、aba、baba。</p>
<p>所以，公共前后缀有：a、aba，最长公共前后缀就是：aba，所以next[5]=3。</p>
<p>举个:chestnut:.</p>
<p>对下面模式串求<strong>next数组</strong>：</p>
<p><img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20220330092317.png" alt="image-20220330164334731"></p>
<p>求方式2的流程跟方式1是类似的，在此处不再赘述（因为过程口述起来实在是比较麻烦）。</p>
<p>方式2的代码为</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] getNext(String pattern) &#123;</span><br><span class="line">    <span class="keyword">int</span> len = pattern.length();</span><br><span class="line">    <span class="keyword">if</span> (len == <span class="number">1</span>) &#123;</span><br><span class="line">        <span class="comment">// 如果模式串长度为 1，直接返回即可</span></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;-<span class="number">1</span>&#125;;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">char</span>[] chars = pattern.toCharArray();</span><br><span class="line">    <span class="keyword">int</span>[] next = <span class="keyword">new</span> <span class="keyword">int</span>[len];</span><br><span class="line">    next[<span class="number">0</span>] = -<span class="number">1</span>;</span><br><span class="line">    next[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">//i = next 待赋值位置 ， j = next[i - 1] = 0,代表&#123;0，i-2&#125;区间的最长公共前后缀长度</span></span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">2</span>, j = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (i &lt; len) &#123;</span><br><span class="line">        <span class="keyword">if</span> (chars[i - <span class="number">1</span>] == chars[j]) &#123;</span><br><span class="line">            <span class="comment">// 判断chars[j]和chars[i-1]是否相等，相等的话，最大的公共前后缀长度+1，直接给next[i]赋值</span></span><br><span class="line">            <span class="comment">// 例：aab，</span></span><br><span class="line">            next[i++] = ++j;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (j &gt; <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="comment">// j &gt; 0, j回滚</span></span><br><span class="line">            j = next[j];</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// j = 0,不能继续回滚了，此时只能设置next为0</span></span><br><span class="line">            next[i++] = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> next;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="方式3"><a href="#方式3" class="headerlink" title="方式3"></a>方式3</h4><p>求出方式1后，循环-1即可。直接求的方法，还没有研究，但是代码如下（没有验证）：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">getNextM3</span><span class="params">(String needle)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// len &gt;= 2</span></span><br><span class="line">    <span class="keyword">char</span>[] chars = needle.toCharArray();</span><br><span class="line">    <span class="keyword">int</span>[] next = <span class="keyword">new</span> <span class="keyword">int</span>[chars.length];</span><br><span class="line">    next[<span class="number">0</span>] = -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">int</span> k = -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; chars.length; ++i) &#123;</span><br><span class="line">        <span class="keyword">while</span> (k != -<span class="number">1</span> &amp;&amp; chars[k + <span class="number">1</span>] != chars[i]) &#123;</span><br><span class="line">            k = next[k];</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (chars[k + <span class="number">1</span>] == chars[i]) &#123;</span><br><span class="line">            ++k;</span><br><span class="line">        &#125;</span><br><span class="line">        next[i] = k;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<h2 id="BM算法"><a href="#BM算法" class="headerlink" title="BM算法"></a>BM算法</h2><blockquote>
<p>在用于查找子字符串的算法当中，BM（Boyer-Moore）算法被认为最高效的字符串搜索算法，它由Bob Boyer和J Strother Moore设计于1977年。</p>
<p>一般情况下，比KMP算法快3-5倍。</p>
<p>BM算法常用于文本编辑器中的搜索匹配功能，比如大家所熟知的GNU grep命令使用的就是该算法，这也是GNU grep比BSD grep快的一个重要原因。</p>
<p>也可以叫做BadMatch，因为BM算法是关于坏字符的匹配。</p>
</blockquote>
<h2 id="快慢指针"><a href="#快慢指针" class="headerlink" title="快慢指针"></a>快慢指针</h2>
      
    </div><!-- .entry-content -->

    <footer class="entry-meta">
    <a href="/2021/09/15/DateStructor/">
    <time datetime="2021-09-14T16:00:00.000Z" class="entry-date">
        2021-09-15
    </time>
</a>
    
    
    </footer>
</article>


    
<nav class="nav-single">
    <h3 class="assistive-text">文章导航</h3>
    
        <span class="nav-previous"><a href="/2022/01/11/Redis/" rel="prev"><span class="meta-nav">←</span> Redis</a></span>
    
    
        <span class="nav-next"><a href="/2021/09/15/Linux/" rel="next">Linux学习 <span class="meta-nav">→</span></a></span>
    
</nav><!-- .nav-single -->






<section id="comments">
  <!-- 多说评论框 start -->
  <div class="ds-thread" data-thread-key="post-DateStructor" data-title="Date Structor ---  数据结构" data-url="https://masuo777.github.io/2021/09/15/DateStructor/"></div>
  <!-- 多说评论框 end -->
  <!-- 多说公共JS代码 start (一个网页只需插入一次) -->
  <script type="text/javascript">
  var duoshuoQuery = {short_name:'ms'};
    (function() {
	  var ds = document.createElement('script');
	  ds.type = 'text/javascript';ds.async = true;
	  ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
	  ds.charset = 'UTF-8';
	  (document.getElementsByTagName('head')[0]
	   || document.getElementsByTagName('body')[0]).appendChild(ds);
    })();
  </script>
  <!-- 多说公共JS代码 end -->
</section>


</div></div>
        <div id="secondary" class="widget-area" role="complementary">
  
    <aside class="widget">
    <h3 class="widget-title">CONTACT ME</h3>
    <div class="widget-content">
      <p>邮箱：masuo0.0@foxmail.com</p>
      <p>QQ：2919029885</p>
      <a target="_blank" rel="noopener" href="https://www.cnblogs.com/msdog/">博客园</a>
      </br>
      <img src="https://masuo-github-image.oss-cn-beijing.aliyuncs.com/image/20210701223301.jpg" height="250px"/>
      
    </div>
</aside>
  
    <aside class="widget">
    <h3 class="widget-title">赞助我</h3>
    <div class="widget-content">
      <img src='/css/images/alipay.png' style='width:100%;' />
    </div>
</aside>
  
    <aside class="widget">
    <h3 class="widget-title">公众号</h3>
    <div class="widget-content">
      <p>暂时没有，待我代码行数100000，我可能才有这个资格吧。</p>
      <p></p>
    </div>
</aside>
  
</div>
      </div>
      <footer id="colophon" role="contentinfo">
    <p>&copy; 2022 John Doe; All rights reserved.</p>
    <p>Powered by <a href="http://hexo.io/" target="_blank">Hexo</a></p>
</footer>
    <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"1","bdMiniList":false,"bdPic":"","bdStyle":"2","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script>

<script src="/js/jquery-2.0.3.min.js"></script>


  
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>




<script src="/js/script.js"></script>


<script src="/js/navigation.js"></script>

<div id="bg"></div>

  </div>
</body>
</html>